class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(nullptr));
        return qsort_topk(nums, 0, nums.size() - 1, k);
    }
 
    int qsort_topk(vector<int>& nums, int begin, int end, int k)
    {   // 到begin和end区间找第k大元素
        if(begin == end)
            return nums[begin];
 
        int key = nums[rand() % (end - begin + 1) + begin];
        int i = begin, left = begin - 1, right = end + 1;
        while(i < right)
        {
            if(nums[i] < key)
                swap(nums[++left], nums[i++]);
            else if(nums[i] == key)
                i++;
            else
                swap(nums[--right], nums[i]);
        }
 
        // [begin, left] [left+1, right-1] [rignt, end]
        int c = end - right + 1; // 右区间元素个数
        int b = right - left - 1; // 中间区间元素个数
        if(c >= k) // 右区间元素个数>=k，到右区间找
            return qsort_topk(nums, right, end, k);
        else if(b + c >= k) // 右两区间元素个数>=k，返回中间区间元素
            return key;
        else  // 到左区间找第k-b-c大的
            return qsort_topk(nums, begin, left, k - b - c);
    }
};